import java.util.List;
import java.util.PriorityQueue;

//合并k个升序链表
//https://leetcode.cn/problems/merge-k-sorted-lists/description/
public class Test {
    public static void main(String[] args) {
        //
    }
}


//Definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}


//方法一：优先级队列（小根堆）
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        //先创建一个优先级队列
        PriorityQueue<ListNode> queue = new PriorityQueue<>((v1,v2)->v1.val-v2.val);


        int len = lists.length;//链表个数
        //将每个链表的头结点添加到优先级队列
        for (int i = 0; i < len; i++) {
            if( lists[i] != null) queue.offer(lists[i]);
        }

        //有问题（1）
//        ListNode head = queue.poll();
//        ListNode curTail = head;
//        ListNode curHead = curTail;
//
//        while(!queue.isEmpty()){
//            if(curHead.next!=null){
//                queue.add(curHead.next);
//                curHead = curHead.next;
//            }
//            curTail.next = queue.poll();
//            curTail = curTail.next;
//
//        }
//        return head;

        ListNode ret = new ListNode(0);//虚拟头节点
        ListNode cur = ret;
        while(!queue.isEmpty()){
            cur.next = queue.poll();
            cur = cur.next;
            ListNode tmp = cur;
            if(tmp.next != null){
                queue.offer(tmp.next);
            }
        }
        return ret.next;
    }
}

//解法二：分治-递归（归并排序用过）
class Solution2 {
    public ListNode mergeKLists(ListNode[] lists) {
        //
        return merge(ListNode[] lists,0,lists.length-1);
    }
    private ListNode merge(ListNode[] lists,int left,int right){
        //
        if(left > right) return null;
        if(left == right) return lists[left];

        //1.平分数组
        int mid = (left + right)/2;
        //[left,mid] [mid+1,right]

        //2.分别处理
        ListNode cur1 = merge(lists,left,mid);
        ListNode cur2 = merge(lists,mid+1,right);

        //3.合并
        ListNode head = new ListNode(0);
        ListNode cur = head;
        while (cur1!=null && cur2!=null){
            if(cur1.val > cur2.val){
                cur.next = cur2;
                cur2 = cur2.next;
                cur = cur.next;//这句可以抽出来（公共）
            }else{
                cur.next = cur1;
                cur1 = cur1.next;
                cur = cur.next;
            }
        }
        while(cur1 != null){
            cur.next = cur1;
            cur1 = cur1.next;
            cur = cur.next;
        }
        while(cur2 != null){
            cur.next = cur2;
            cur2 = cur2.next;
            cur = cur.next;
        }
        return head.next;
    }
}
